package cn.zifangsky.stack.questions;

import cn.zifangsky.stack.LinkStack;
import cn.zifangsky.stack.Stack;
import org.junit.Test;

/**
 * 汉诺塔问题的两种求解方式（限制不能从最左侧的塔直接移动到最右侧，也不能从最右侧直接移动到最左侧，而是必须经过中间）
 * 求当塔有N 层的时候，打印最优移动过程和最优移动总步数。
 *
 * <p>例如，当塔数为两层时，最上层的塔记为1，最下层的塔记为2，则打印：</p>
 * <ul>
 *     <li>Move 1 from left to mid</li>
 *     <li>Move 1 from mid to right</li>
 *     <li>Move 2 from left to mid</li>
 *     <li>Move 1 from right to mid</li>
 *     <li>Move 1 from mid to left</li>
 *     <li>Move 2 from mid to right</li>
 *     <li>Move 1 from left to mid</li>
 *     <li>Move 1 from mid to right</li>
 *     <li>It will move 8 steps.</li>
 * </ul>
 *
 * @author zifangsky
 * @date 2019/12/19
 * @since 1.0.0
 */
public class Problem_007_HanoiStack {

    @Test
    public void testMethods(){
        //解法一：使用递归求解
        int steps1 = this.solution1(2, "left", "mid", "right");
        System.out.println("It will move " + steps1 + " steps.");
        System.out.println("***********************************");

        //解法二：使用栈求解
        int steps2 = this.solution2(2, "left", "mid", "right");
        System.out.println("It will move " + steps2 + " steps.");
        System.out.println("***********************************");
    }


    /**
     * 【解汉诺塔问题】解法一：使用递归求解
     * @author zifangsky
     * @date 2019/12/19 16:23
     * @since 1.0.0
     * @param num 塔的层数
     * @param left 左边塔的名称
     * @param mid 中间塔的名称
     * @param right 右边塔的名称
     * @return int 最优移动总步数
     */
    private int solution1(int num, String left, String mid, String right){
        if(num < 1){
            return 0;
        }

        //求解：从左边移到右边
        return this.process(num, left, mid, right, left, right);
    }

    /**
     *
     * <p>如果剩下N 层塔，从最上到最下依次为1～N ，则有如下判断：</p>
     * <p>情况1：如果剩下的N 层塔都在“左”，希望全部移到“中”，则有三个步骤:</p>
     * <ol>
     *     <li>将1～N -1层塔先全部从“左”移到“右”（使用递归实现）。</li>
     *     <li>将第N 层塔从“左”移到“中”。</li>
     *     <li>再将1～N -1层塔全部从“右”移到“中”（使用递归实现）。</li>
     * </ol>
     *
     * <p>情况2：如果把剩下的N 层塔从“中”移到“左”，从“中”移到“右”，从“右”移到“中”，过程与情况1同理，一样是分解为三步，在此不再详述。</p>
     *
     * <p>情况3：如果剩下的N 层塔都在“左”，希望全部移到“右”，则有五个步骤：</p>
     * <ol>
     *     <li>将1～N -1层塔先全部从“左”移到“右”（使用递归实现）。</li>
     *     <li>将第N 层塔从“左”移到“中”。</li>
     *     <li>再将1～N -1层塔全部从“右”移到“左”（使用递归实现）。</li>
     *     <li>将第N 层塔从“中”移到“右”。</li>
     *     <li>最后将1～N -1层塔全部从“左”移到“右”（使用递归实现）。</li>
     * </ol>
     *
     * <p>情况4：如果剩下的N 层塔都在“右”，希望全部移到“左”，过程与情况3同理，一样是分解为五步，在此不再详述。</p>
     *
     * @author zifangsky
     * @date 2019/12/19 16:26
     * @since 1.0.0
     * @param num 塔的层数
     * @param left 左边塔的名称
     * @param mid 中间塔的名称
     * @param right 右边塔的名称
     * @param from 移动的起始点
     * @param to 移动的终点
     * @return int 最优移动总步数
     */
    private int process(int num, String left, String mid, String right,
                        String from, String to){
        //1. 如果只有一个时，直接打印输出
        if(num == 1){
            //1.1 “中到左”、“中到右”、“左到中”、“右到中”这四种情况，只需要一步实现
            if(from.equals(mid) || to.equals(mid)){
                System.out.println("Move 1 from " + from + " to " + to);
                return 1;
            }
            //1.2 “左到右”、“右到左”这两种情况，需要两步实现
            else{
                System.out.println("Move 1 from " + from + " to " + mid);
                System.out.println("Move 1 from " + mid + " to " + to);
                return 2;
            }
        }

        //2. 如果有多层塔，则需要使用递归逐步移动
        //2.1 “中到左”、“中到右”、“左到中”、“右到中”这四种情况，需要三个步骤实现（详见方法注释）
        if(from.equals(mid) || to.equals(mid)){
            //判断空闲的另一个塔具体是哪一个
            String another = (to.equals(left) || from.equals(left)) ? right : left;

            int step1 = this.process(num - 1, left, mid, right, from, another);

            int step2 = 1;
            System.out.println("Move " + num + " from " + from + " to " + to);

            int step3= this.process(num - 1, left, mid, right, another, to);

            return step1 + step2 + step3;
        }
        //2.2 “左到右”、“右到左”这两种情况，需要五个步骤实现（详见方法注释）
        else{
            int step1 = this.process(num - 1, left, mid, right, from, to);

            int step2 = 1;
            System.out.println("Move " + num + " from " + from + " to " + mid);

            int step3 = this.process(num - 1, left, mid, right, to, from);

            int step4 = 1;
            System.out.println("Move " + num + " from " + mid + " to " + to);

            int step5 = this.process(num - 1, left, mid, right, from, to);

            return step1 + step2 + step3 + step4 + step5;
        }
    }




    /**
     * 【解汉诺塔问题】解法二：使用栈求解
     *
     * <p>如果我们把左、中、右三个地点抽象成栈，依次记为LS、MS和RS。
     * 最初所有的塔都在LS上，移动规则只有“中到左”、“中到右”、“左到中”、“右到中”这四个动作。
     * 也就是：某一个栈（from）把栈顶元素弹出，然后压入到另一个栈里（to），作为这一个栈（to）的栈顶。</p>
     *
     * <p>那么，我们可以推导出如下几条规则：</p>
     * <ol>
     *     <li>规则一：不可以大的压在小的上面。</li>
     *     <li>规则二：相邻2步操作不可逆。</li>
     *     <li>规则三：游戏的第一个动作一定是L->M，这是显而易见的。</li>
     *     <li>规则三：在走出最少步数过程中的任何时刻，四个动作中只有一个动作不违反“大的压在小的上面”和“相邻不可逆原则”，另外三个动作一定都会违反。</li>
     * </ol>
     *
     * @author zifangsky
     * @date 2019/12/20 10:12
     * @since 1.0.0
     * @param num 塔的层数
     * @param left 左边塔的名称
     * @param mid 中间塔的名称
     * @param right 右边塔的名称
     * @return int 最优移动总步数
     */
    private int solution2(int num, String left, String mid, String right){
        if(num < 1){
            return 0;
        }

        //1. 给左、中、右三个塔分别初始化一个栈
        Stack<Integer> leftStack = new LinkStack<>();
        Stack<Integer> midStack = new LinkStack<>();
        Stack<Integer> rightStack = new LinkStack<>();
        leftStack.push(Integer.MAX_VALUE);
        midStack.push(Integer.MAX_VALUE);
        rightStack.push(Integer.MAX_VALUE);

        //2. 将N层塔放在左边栈中
        for(int i = num; i > 0; i--){
            leftStack.push(i);
        }

        //3. 初始化一个默认的“上一次的移动动作”
        Holder<Action> preActHolder = new Holder<>(Action.No);

        //4. 开始游戏的移动过程
        int step = 0;
        //一直到N层塔都移动到右边栈，游戏才结束
        while (rightStack.size() < (num + 1)){
            //第一步肯定是L->M
            step += this.move(preActHolder, Action.L_TO_M, leftStack, midStack, left, mid);
            step += this.move(preActHolder, Action.M_TO_L, midStack, leftStack, mid, left);
            step += this.move(preActHolder, Action.R_TO_M, rightStack, midStack, right, mid);
            step += this.move(preActHolder, Action.M_TO_R, midStack, rightStack, mid, right);
        }

        //返回最优移动总步数
        return step;
    }

    /**
     * 抽象出来的移动规则
     * @author zifangsky
     * @date 2019/12/20 11:39
     * @since 1.0.0
     * @param preActHolder 上一次的移动动作
     * @param act 本次想要移动的动作
     * @param fromStack 移动动作起点对应的栈
     * @param toStack 移动动作终点对应的栈
     * @param from 移动的起始点
     * @param to 移动的终点
     * @return int 最优移动总步数
     */
    private int move(Holder<Action> preActHolder, Action act,
                     Stack<Integer> fromStack, Stack<Integer> toStack,
                     String from, String to){
        //1. 获取上次动作的逆反动作
        Action reverseAct = Action.getReverseAction(preActHolder.value);

        //2. 判断可以移动的条件：“相邻2步操作不可逆” 且 “不可以小压大”
        if(reverseAct != act && fromStack.top() < toStack.top()){
            toStack.push(fromStack.pop());
            preActHolder.value = act;

            System.out.println("Move " + toStack.top() + " from " + from + " to " + to);
            return 1;
        }

        return 0;
    }

    /**
     * 定义游戏过程中可能出现的四个动作
     */
    enum Action{
        /**
         * 初始还没有开始移动的状态
         */
        No,
        /**
         * 左到中
         */
        L_TO_M,
        /**
         * 中到左
         */
        M_TO_L,
        /**
         * 右到中
         */
        R_TO_M,
        /**
         * 中到右
         */
        M_TO_R;

        /**
         * 获取某个动作的逆反动作
         */
        static Action getReverseAction(Action act){
            switch (act){
                case L_TO_M: return M_TO_L;
                case M_TO_L: return L_TO_M;
                case R_TO_M: return M_TO_R;
                case M_TO_R: return R_TO_M;
                default: return No;
            }
        }
    }

    /**
     * 定义一个Holder，用于方法内改变一个对象
     */
    class Holder<T> {

        T value;

        Holder() {
        }

        Holder(T value) {
            this.value = value;
        }
    }

}
